{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Letter Combinations of a Phone Number"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #string #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #字符串 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: letterCombinations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #电话号码的字母组合"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个仅包含数字&nbsp;<code>2-9</code>&nbsp;的字符串，返回所有它能表示的字母组合。答案可以按 <strong>任意顺序</strong> 返回。</p>\n",
    "\n",
    "<p>给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。</p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/11/09/200px-telephone-keypad2svg.png\" style=\"width: 200px;\" /></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>digits = \"23\"\n",
    "<strong>输出：</strong>[\"ad\",\"ae\",\"af\",\"bd\",\"be\",\"bf\",\"cd\",\"ce\",\"cf\"]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>digits = \"\"\n",
    "<strong>输出：</strong>[]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>digits = \"2\"\n",
    "<strong>输出：</strong>[\"a\",\"b\",\"c\"]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= digits.length &lt;= 4</code></li>\n",
    "\t<li><code>digits[i]</code> 是范围 <code>['2', '9']</code> 的一个数字。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [letter-combinations-of-a-phone-number](https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [letter-combinations-of-a-phone-number](https://leetcode.cn/problems/letter-combinations-of-a-phone-number/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"23\"', '\"\"', '\"2\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCombinations(self, digits: str) -> List[str]:\n",
    "        lettersMap = {'2':'abc', '3':'def', '4':'ghi', '5':'jkl', '6':'mno', '7':'pqrs', '8':'tuv','9':'wxyz'}\n",
    "        ans = []\n",
    "        if not digits or '1' in digits or '0' in digits:\n",
    "            return ans\n",
    "        \n",
    "        def getComb(number, res):\n",
    "            if number:\n",
    "                for letter in lettersMap[number[0]]:\n",
    "                    getComb(number[1:], res + letter)\n",
    "            else:\n",
    "                ans.append(res)\n",
    "                \n",
    "        getComb(digits, '')\n",
    "        return ans\n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def letterCombinations(self, digits: 'str') -> 'List[str]':\n",
    "#         table = {\"2\":[a,b,c],}\n",
    "#         result = ['']*(len(digits)**2)\n",
    "#         for i in range(len(digits)*3):\n",
    "#             for index,word in enumarate(digits):\n",
    "#                 result[i] = result[i] + table[word][index]\n",
    "class Solution:\n",
    "    def letterCombinations(self, digits):\n",
    "        \"\"\"\n",
    "        :type digits: str\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        if not digits:\n",
    "            return []\n",
    "\n",
    "        digit2chars={\n",
    "            '2':'abc',\n",
    "            '3':'def',\n",
    "            '4':'ghi',\n",
    "            '5':'jkl',\n",
    "            '6':'mno',\n",
    "            '7':'pqrs',\n",
    "            '8':'tuv',\n",
    "            '9':'wxyz'\n",
    "        }\n",
    "\n",
    "        if len(digits)==1:\n",
    "            return list(digit2chars[digits])\n",
    "        res = [ i for i in digit2chars[digits[0]]]\n",
    "        \n",
    "        #遍历每一个数字\n",
    "        for i in digits[1:]:\n",
    "        #m+n:m和n的不重叠组合\n",
    "        #for m in res:  迭代 前面所有数字对应字母的组合\n",
    "        #for n in digit2chars[i]:当前数字对应的所有字母\n",
    "\n",
    "            res = [ m+n for m in res for n in digit2chars[i] ]\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCombinations(self, digits):\n",
    "        dict = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}\n",
    "\n",
    "        result = [''] if len(digits) > 0 else []\n",
    "        for i in digits:\n",
    "            temp_comb = []\n",
    "            for r in result:\n",
    "                for d in dict[i]:\n",
    "                    temp_comb.append(r+d)\n",
    "            result = temp_comb\n",
    "\n",
    "        return result\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCombinations(self, digits):\n",
    "        \"\"\"\n",
    "        :type digits: str\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        num2str = []\n",
    "        num2str.append(\"\")\n",
    "        num2str.append(\"\")\n",
    "        num2str.append([\"a\",\"b\",\"c\"])\n",
    "        num2str.append([\"d\",\"e\",\"f\"])\n",
    "        num2str.append([\"g\",\"h\",\"i\"])\n",
    "        num2str.append([\"j\",\"k\",\"l\"])\n",
    "        num2str.append([\"m\",\"n\",\"o\"])\n",
    "        num2str.append([\"p\",\"q\",\"r\", \"s\"])\n",
    "        num2str.append([\"t\",\"u\",\"v\"])\n",
    "        num2str.append([\"w\",\"x\",\"y\", \"z\"])\n",
    "        \n",
    "        print(num2str)\n",
    "        result = []\n",
    "        \n",
    "        i = 0\n",
    "        \n",
    "        while i < len(digits) :\n",
    "            index = int(digits[i])\n",
    "            # result = update(result, num2str[index])\n",
    "            temp = []\n",
    "            for a in num2str[index]:\n",
    "                if len(result) == 0:\n",
    "                    temp.append(a)\n",
    "                    continue\n",
    "                    \n",
    "                for b in result:\n",
    "                    temp.append(b+a)\n",
    "                    print(a+b)\n",
    "            result = temp\n",
    "            #\n",
    "            i += 1\n",
    "        \n",
    "        return result\n",
    "    \n",
    "    \n",
    "        def update(result, zifu):\n",
    "            temp = []\n",
    "            for a in zifu:\n",
    "                for b in result:\n",
    "                    temp.append(a+b)\n",
    "                    print(temp)\n",
    "            return temp\n",
    "            \n",
    "            \n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCombinations(self, digits):\n",
    "        \"\"\"\n",
    "        :type digits: str\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        num_dict = {'2':'abc', '3':'def', '4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}\n",
    "        if len(digits) == 0:\n",
    "            return []\n",
    "        if len(digits) == 1:\n",
    "            return list(num_dict[digits[-1]])\n",
    "        prev = self.letterCombinations(digits[:-1])\n",
    "        additional = num_dict[digits[-1]]\n",
    "        return [u+v for u in prev for v in additional]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCombinations(self, digits: str) -> List[str]:\n",
    "        dic = {2:['a','b','c'],\n",
    "               3:['d','e','f'],\n",
    "               4:['g','h','i'],\n",
    "               5:['j','k','l'],\n",
    "               6:['m','n','o'],\n",
    "               7:['p','q','r','s'],\n",
    "               8:['t','u','v'],\n",
    "               9:['w','x','y','z']}\n",
    "        res_str = []\n",
    "        if(len(digits)==0):   return res_str\n",
    "        if(len(digits)==1):\n",
    "            return dic[int(digits[0])]\n",
    "        result = self.letterCombinations(digits[1:])\n",
    "        for r in result:\n",
    "            for j in dic[int(digits[0])]:\n",
    "                res_str.append(j+r)\n",
    "        return res_str"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCombinations(self, digits: str) -> List[str]:\n",
    "        if len(digits) == 0:\n",
    "            return []\n",
    "        n2s = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}\n",
    "        res = ['']\n",
    "        for d in digits:\n",
    "            n = len(res)\n",
    "            for j in n2s[d][1:]:\n",
    "                for k in range(n):\n",
    "                    res.append(res[k] + j)\n",
    "            for k in range(n):\n",
    "                res[k] += n2s[d][0]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCombinations(self, digits: str) -> List[str]:\n",
    "        dic = {'2': ['a', 'b', 'c'],\n",
    "               '3': ['d', 'e', 'f'],\n",
    "               '4': ['g', 'h', 'i'],\n",
    "               '5': ['j', 'k', 'l'],\n",
    "               '6': ['m', 'n', 'o'],\n",
    "               '7': ['p', 'q', 'r', 's'],\n",
    "               '8': ['t', 'u', 'v'],\n",
    "               '9': ['w', 'x', 'y', 'z'],\n",
    "              }\n",
    "        if len(digits) == 0: return []\n",
    "        res = ['']\n",
    "        for n in digits:\n",
    "            res = [r + v for r in res for v in dic[n]]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCombinations(self, digits: str) -> List[str]:\n",
    "        lst = []\n",
    "        dict = {2:\"abc\",3:'def',4:'ghi',5:'jkl',6:'mno',7:'pqrs',\n",
    "                8:'tuv',9:'wxyz'}\n",
    "        n = len(digits)\n",
    "        #如果为0，返回空\n",
    "        if n == 0:\n",
    "            return lst\n",
    "        #存储第一个数的字母\n",
    "        str_0 = dict.get(int(digits[0]))        \n",
    "        for i in range(0,len(str_0)):\n",
    "            lst.append(str_0[i])\n",
    "        #若长度为1\n",
    "        if n == 1: return lst\n",
    "        #考虑从1往后的字符\n",
    "        #取第一个字符的字母     \n",
    "        for i in digits[1:]:                                            \n",
    "            lst = [ m+n for m in lst for n in dict[int(i)] ]\n",
    "        return lst\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCombinations(self, digits):\n",
    "        \"\"\"\n",
    "        :type digits: str\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        if len(digits) == 0:\n",
    "            return []\n",
    "\n",
    "        phone = {'2': ['a', 'b', 'c'],\n",
    "                 '3': ['d', 'e', 'f'],\n",
    "                 '4': ['g', 'h', 'i'],\n",
    "                 '5': ['j', 'k', 'l'],\n",
    "                 '6': ['m', 'n', 'o'],\n",
    "                 '7': ['p', 'q', 'r', 's'],\n",
    "                 '8': ['t', 'u', 'v'],\n",
    "                 '9': ['w', 'x', 'y', 'z']}\n",
    "        results = []\n",
    "\n",
    "        def func(n, res, digits):\n",
    "            if n == len(digits):\n",
    "                # print(res)\n",
    "                # res = \"\".join(res)\n",
    "                # print(res)\n",
    "                #\n",
    "                # global results\n",
    "                results.append(\"\".join(res))\n",
    "                # print(results)\n",
    "                return\n",
    "\n",
    "            for ch in phone[digits[n]]:\n",
    "                # res[n] = ch\n",
    "                func(n+1, res + [ch], digits)\n",
    "\n",
    "        func(0, [], digits)\n",
    "\n",
    "        return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCombinations(self, digits: str) -> list:\n",
    "        x = ['abc','def','ghi','jkl','mno','pqrs','tuv','wxyz']\n",
    "        if len(digits)==0 :return []\n",
    "        res=list(x[int(digits[0])-2])\n",
    "        # res = list(res)\n",
    "        digits = list(digits)\n",
    "        digits.pop(0)\n",
    "        while(digits):\n",
    "            temp = []\n",
    "            temp = [p+va for va in list(x[int(digits[0])-2]) for p in res]\n",
    "            res = temp\n",
    "            digits.pop(0)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCombinations(self, digits: str) -> List[str]:\n",
    "        if len(digits)==0:\n",
    "            return []\n",
    "        l = ['abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']\n",
    "        index = int(digits[0])\n",
    "        l1 = []\n",
    "        l2 = []\n",
    "        for c in l[index-2]:\n",
    "            l1.append(c)\n",
    "        for i in range(1, len(digits)):\n",
    "            index = int(digits[i])\n",
    "            for j in range(len(l1)):\n",
    "                s = l1.pop()\n",
    "                print(s, l1)\n",
    "                for c in l[index-2]:\n",
    "                    l2.append(s+c)\n",
    "            l1, l2 = l2, []\n",
    "        return l1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCombinations(self, digits: str) -> List[str]:\n",
    "        if digits == \"\": return []\n",
    "        digit2char = {\n",
    "            '2': ['a', 'b', 'c'],\n",
    "            '3': ['d', 'e', 'f'],\n",
    "            '4': ['g', 'h', 'i'],\n",
    "            '5': ['j', 'k', 'l'],\n",
    "            '6': ['m', 'n', 'o'],\n",
    "            '7': ['p', 'q', 'r', 's'],\n",
    "            '8': ['t', 'u', 'v'],\n",
    "            '9': ['w', 'x', 'y', 'z'],\n",
    "        }\n",
    "        candidates = []\n",
    "        for digit in digits:\n",
    "            char_list = digit2char[digit]\n",
    "            candidates.append(char_list)\n",
    "        from itertools import product\n",
    "        res = []\n",
    "        for _ in product(*candidates):\n",
    "            res.append(''.join(_))\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCombinations(self, digits: str) -> List[str]:\n",
    "        conversion={'2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}  # 字典\n",
    "        if len(digits)==0:\n",
    "            return [] \n",
    "        product=['']\n",
    "        for k in digits:\n",
    "            product=[i+j for i in product for j in conversion[k]]\n",
    "        return product\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCombinations(self, digits: str) -> List[str]:\n",
    "        if not digits:\n",
    "            return list()\n",
    "        phoneMap = {\"2\": \"abc\", \"3\": \"def\", \"4\": \"ghi\", \"5\": \"jkl\",\n",
    "                    \"6\": \"mno\", \"7\": \"pqrs\", \"8\": \"tuv\", \"9\": \"wxyz\"}\n",
    "\n",
    "        def findConbinattion(index: int):\n",
    "            if index == len(digits):\n",
    "                combinations.append(\"\".join(combination))\n",
    "            else:\n",
    "                digit = digits[index]\n",
    "                for l in phoneMap[digit]:\n",
    "                    combination.append(l)\n",
    "                    findConbinattion(index + 1)\n",
    "                    combination.pop()\n",
    "                    \n",
    "        combinations = list()\n",
    "        combination = list()\n",
    "        findConbinattion(0)\n",
    "        return combinations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "class Solution:\n",
    "    def letterCombinations(self, digits: str) -> List[str]:\n",
    "        self.letterMap = {\n",
    "            '1': ' ', # 0\n",
    "            '2': '', # 1\n",
    "            '2': 'abc', # 2 \n",
    "            '3': 'def', # 3\n",
    "            '4': 'ghi', # 4\n",
    "            '5': 'jkl', # 5\n",
    "            '6': 'mno', # 6\n",
    "            '7': 'pqrs', # 7\n",
    "            '8': 'tuv', # 8\n",
    "            '9': 'wxyz' # 9\n",
    "        }\n",
    "        self.res = []\n",
    "        if not digits: return self.res \n",
    "        self.findCombination(digits, 0, '')\n",
    "        return self.res \n",
    "    @functools.lru_cache(None)\n",
    "    def findCombination(self, digits, index, s):\n",
    "        # s中保存了此时digits[0,...,index-1]翻译得到的一个字母字符串\n",
    "        # 寻找和gitgits[index]匹配的字母，获得digits[0, ..., index]翻译得到的解\n",
    "        # 递归终止条件\n",
    "        if index == len(digits):\n",
    "            # 保存s\n",
    "            self.res.append(s)\n",
    "            return\n",
    "        # 首先处理递归问题\n",
    "        c = digits[index]\n",
    "        assert c>='0' and c<='9' and c!='1'\n",
    "        letters = self.letterMap[c]\n",
    "        for i in range(len(letters)):\n",
    "            self.findCombination(digits, index+1, s+letters[i]) # 递归\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import pdb\n",
    "\n",
    "class Solution:\n",
    "    def letterCombinations(self, digits: str):\n",
    "        \n",
    "        if not digits:\n",
    "            return []\n",
    "        \n",
    "        mapping = {2:['a', 'b', 'c'],\n",
    "                   3:['d', 'e', 'f'],\n",
    "                   4:['g', 'h', 'i'],\n",
    "                   5:['j', 'k', 'l'],\n",
    "                   6:['m', 'n', 'o'],\n",
    "                   7:['p', 'q', 'r', 's'],\n",
    "                   8:['t', 'u', 'v'],\n",
    "                   9:['w', 'x', 'y', 'z']}\n",
    "        pools = [mapping[int(i)] for i in digits]\n",
    "        buff = [[]]\n",
    "        results = []\n",
    "        for pool in pools:\n",
    "            buff = [x+[y] for x in buff for y in pool]\n",
    "        for i in buff:\n",
    "            results.append(''.join(i))\n",
    "        \n",
    "        return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCombinations(self, digits: str) -> List[str]:\n",
    "        results=[]\n",
    "        char_dict = {'2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}\n",
    "        for d in digits:\n",
    "            tmp = []\n",
    "            for char in char_dict[d]:\n",
    "                if len(results) == 0:\n",
    "                    tmp.append(char)\n",
    "                else:\n",
    "                    for res in results:\n",
    "                        tmp.append(res+char)\n",
    "            results = tmp\n",
    "        return results\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCombinations(self, digits: str) -> List[str]:\n",
    "        if not digits:\n",
    "            return []\n",
    "        hash_map = {\n",
    "            '2': 'abc',\n",
    "            '3': 'def',\n",
    "            '4': 'ghi',\n",
    "            '5': 'jkl',\n",
    "            '6': 'mno',\n",
    "            '7': 'pqrs',\n",
    "            '8': 'tuv',\n",
    "            '9': 'wxyz'\n",
    "        }\n",
    "        global path, result\n",
    "        path, result = [], []\n",
    "        def backtracking(digits, index):\n",
    "            if index == len(digits):\n",
    "                return result.append(''.join(path))\n",
    "            for i in hash_map[digits[index]]:\n",
    "                path.append(i)\n",
    "                backtracking(digits, index+1)\n",
    "                path.pop()\n",
    "        backtracking(digits, 0)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import reduce\n",
    "class Solution:\n",
    "    fn = lambda x, y: [i+j for i in x for j in y]\n",
    "    def letterCombinations(self, digits: str) -> List[str]:\n",
    "        digit2chars = {\n",
    "            '2': \"abc\",\n",
    "            '3': \"def\",\n",
    "            '4': \"ghi\",\n",
    "            '5': \"jkl\",\n",
    "            '6': \"mno\",\n",
    "            '7': \"pqrs\",\n",
    "            '8': \"tuv\",\n",
    "            '9': \"wxyz\"\n",
    "        }\n",
    "        if len(digits) < 2:\n",
    "            return [c  for d in digits for c in digit2chars[d]]\n",
    "        return reduce(Solution.fn, [digit2chars[d] for d in digits])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mapping={\"2\":\"abc\",\"3\":\"def\",\"4\":\"ghi\",\"5\":\"jkl\",\"6\":\"mno\",\"7\":\"pqrs\",\"8\":\"tuv\",\"9\":\"wxyz\"}\n",
    "\n",
    "class Solution:\n",
    "    def letterCombinations(self, digits: str) -> List[str]:\n",
    "        res=[]\n",
    "        path=\"\"\n",
    "        n=len(digits)\n",
    "        if digits==\"\":\n",
    "            return []\n",
    "        def backtrack(idx,path):\n",
    "            if idx==n:\n",
    "                res.append(path)\n",
    "                return\n",
    "\n",
    "            for ch in mapping[digits[idx]]:\n",
    "\n",
    "                backtrack(idx+1,path+ch)\n",
    "        backtrack(0,path)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# DFS回溯法\r\n",
    "class Solution:\r\n",
    "    def letterCombinations(self, digits: str) -> List[str]:\r\n",
    "        if not digits: return []\r\n",
    "\r\n",
    "        phoneMap = {\"2\": \"abc\",\r\n",
    "                    \"3\": \"def\",\r\n",
    "                    \"4\": \"ghi\",\r\n",
    "                    \"5\": \"jkl\",\r\n",
    "                    \"6\": \"mno\",\r\n",
    "                    \"7\": \"pqrs\",\r\n",
    "                    \"8\": \"tuv\",\r\n",
    "                    \"9\": \"wxyz\",}\r\n",
    "        \r\n",
    "        def backtrack(index: int):\r\n",
    "            if index == len(digits):\r\n",
    "                combinations.append(''.join(combination))\r\n",
    "            else:\r\n",
    "                digit = digits[index]\r\n",
    "                for letter in phoneMap[digit]:\r\n",
    "                    combination.append(letter)\r\n",
    "                    backtrack(index + 1)\r\n",
    "                    combination.pop()\r\n",
    "\r\n",
    "        combination = []\r\n",
    "        combinations = []\r\n",
    "        backtrack(0)\r\n",
    "        return combinations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def letterCombinations(self, digits: str) -> List[str]:\n",
    "        if not digits:\n",
    "            return []\n",
    "\n",
    "        # 定义数字到字母的映射\n",
    "        mapping = {\n",
    "            '2': 'abc',\n",
    "            '3': 'def',\n",
    "            '4': 'ghi',\n",
    "            '5': 'jkl',\n",
    "            '6': 'mno',\n",
    "            '7': 'pqrs',\n",
    "            '8': 'tuv',\n",
    "            '9': 'wxyz'\n",
    "        }\n",
    "\n",
    "        result = ['']\n",
    "\n",
    "        for digit in digits:\n",
    "            temp = []\n",
    "            letters = mapping[digit]\n",
    "            for combination in result:\n",
    "                for letter in letters:\n",
    "                    temp.append(combination + letter)\n",
    "            result = temp\n",
    "\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCombinations(self, digits: str) -> List[str]:\n",
    "        if not digits: return []\n",
    "        phone = ['abc','def','ghi','jkl','mno','pqrs','tuv','wxyz']\n",
    "        queue = ['']\n",
    "\n",
    "        for digit in digits:\n",
    "            for _ in range(len(queue)):\n",
    "                tmp = queue.pop(0)\n",
    "                for letter in phone[ord(digit)-50]:\n",
    "                    queue.append(tmp + letter)\n",
    "        return queue\n",
    "\n",
    "\n",
    "       \n",
    "       \n",
    "\n",
    "\n",
    "     \n",
    "\n",
    "   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    dic = {\"2\": [\"a\", \"b\", \"c\"], \"3\": [\"d\", \"e\", \"f\"], \"4\": [\"g\", \"h\", \"i\"], \"5\": [\"j\", \"k\", \"l\"], \"6\": [\"m\", \"n\", \"o\"],\n",
    "           \"7\": [\"p\", \"q\", \"r\", \"s\"], \"8\": [\"t\", \"u\", \"v\"], \"9\": [\"w\", \"x\", \"y\", \"z\"]}\n",
    "\n",
    "    def letterCombinations(self, digits: str) -> list[str]:\n",
    "        if digits == \"\":\n",
    "            return []\n",
    "        res = []\n",
    "        l = list(digits)\n",
    "        return self.help_1(\"\", l, res)\n",
    "\n",
    "    def help_1(self, s: str, l: list[str], res: list[str]) -> list[str]:\n",
    "        if len(l) == 0:\n",
    "            res.append(s)\n",
    "            return res\n",
    "        t1 = l[0]\n",
    "        t = self.dic[l[0]]\n",
    "        for i in range(len(t)):\n",
    "            s = s + self.dic[l[0]][i]\n",
    "            self.help_1(s, l[1:], res)\n",
    "            s = s[0:len(s) - 1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def letterCombinations(self, digits: str) -> List[str]:\n",
    "        all_maps = {\n",
    "            2:'abc',\n",
    "            3:'def',\n",
    "            4:'ghi',\n",
    "            5:'jkl',\n",
    "            6:'mno',\n",
    "            7:'pqrs',\n",
    "            8:'tuv',\n",
    "            9:'wxyz'\n",
    "        }\n",
    "        if len(digits) == 0:\n",
    "            return []\n",
    "        if len(digits) == 1:\n",
    "            return list(all_maps[int(digits)])\n",
    "\n",
    "\n",
    "        results = self.letterCombinations(digits[1:])\n",
    "\n",
    "        cur_res_list = []\n",
    "        for c in list(all_maps[int(digits[0])]):\n",
    "            for r in results:\n",
    "                cur_res_list.append(c + r)\n",
    "\n",
    "        return cur_res_list\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
